{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# rogo2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/rogo2.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/rogo2.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "  Rogo puzzle solver in Google CP Solver.\n",
    "\n",
    "  From http://www.rogopuzzle.co.nz/\n",
    "  '''\n",
    "  The object is to collect the biggest score possible using a given\n",
    "  number of steps in a loop around a grid. The best possible score\n",
    "  for a puzzle is given with it, so you can easily check that you have\n",
    "  solved the puzzle. Rogo puzzles can also include forbidden squares,\n",
    "  which must be avoided in your loop.\n",
    "  '''\n",
    "\n",
    "  Also see Mike Trick:\n",
    "  'Operations Research, Sudoko, Rogo, and Puzzles'\n",
    "  http://mat.tepper.cmu.edu/blog/?p=1302\n",
    "\n",
    "  Problem instances:\n",
    "  * http://www.hakank.org/google_or_tools/rogo_mike_trick.py\n",
    "  * http://www.hakank.org/google_or_tools/rogo_20110106.py\n",
    "  * http://www.hakank.org/google_or_tools/rogo_20110107.py\n",
    "\n",
    "\n",
    "  Compare with the following models:\n",
    "  * Answer Set Programming:\n",
    "     http://www.hakank.org/answer_set_programming/rogo2.lp\n",
    "  * MiniZinc: http://www.hakank.org/minizinc/rogo2.mzn\n",
    "\n",
    "  This model was created by Hakan Kjellerstrand (hakank@gmail.com)\n",
    "  Also see my other Google CP Solver models:\n",
    "  http://www.hakank.org/google_or_tools/\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import re\n",
    "\n",
    "from ortools.constraint_solver import pywrapcp\n",
    "\n",
    "\n",
    "def main(problem, rows, cols, max_steps):\n",
    "\n",
    "  # Create the solver.\n",
    "  solver = pywrapcp.Solver(\"Rogo grid puzzle\")\n",
    "\n",
    "  #\n",
    "  # data\n",
    "  #\n",
    "  W = 0\n",
    "  B = -1\n",
    "  print(\"rows: %i cols: %i max_steps: %i\" % (rows, cols, max_steps))\n",
    "\n",
    "  problem_flatten = [problem[i][j] for i in range(rows) for j in range(cols)]\n",
    "  max_point = max(problem_flatten)\n",
    "  print(\"max_point:\", max_point)\n",
    "  max_sum = sum(problem_flatten)\n",
    "  print(\"max_sum:\", max_sum)\n",
    "  print()\n",
    "\n",
    "  #\n",
    "  # declare variables\n",
    "  #\n",
    "\n",
    "  # the coordinates\n",
    "  x = [solver.IntVar(0, rows - 1, \"x[%i]\" % i) for i in range(max_steps)]\n",
    "  y = [solver.IntVar(0, cols - 1, \"y[%i]\" % i) for i in range(max_steps)]\n",
    "\n",
    "  # the collected points\n",
    "  points = [\n",
    "      solver.IntVar(0, max_point, \"points[%i]\" % i) for i in range(max_steps)\n",
    "  ]\n",
    "\n",
    "  # objective: sum of points in the path\n",
    "  sum_points = solver.IntVar(0, max_sum)\n",
    "\n",
    "  #\n",
    "  # constraints\n",
    "  #\n",
    "\n",
    "  # all coordinates must be unique\n",
    "  for s in range(max_steps):\n",
    "    for t in range(s + 1, max_steps):\n",
    "      b1 = x[s] != x[t]\n",
    "      b2 = y[s] != y[t]\n",
    "      solver.Add(b1 + b2 >= 1)\n",
    "\n",
    "  # calculate the points (to maximize)\n",
    "  for s in range(max_steps):\n",
    "    solver.Add(points[s] == solver.Element(problem_flatten, x[s] * cols + y[s]))\n",
    "\n",
    "  solver.Add(sum_points == sum(points))\n",
    "\n",
    "  # ensure that there are not black cells in\n",
    "  # the path\n",
    "  for s in range(max_steps):\n",
    "    solver.Add(solver.Element(problem_flatten, x[s] * cols + y[s]) != B)\n",
    "\n",
    "  # get the path\n",
    "  for s in range(max_steps - 1):\n",
    "    solver.Add(abs(x[s] - x[s + 1]) + abs(y[s] - y[s + 1]) == 1)\n",
    "\n",
    "  # close the path around the corner\n",
    "  solver.Add(abs(x[max_steps - 1] - x[0]) + abs(y[max_steps - 1] - y[0]) == 1)\n",
    "\n",
    "  # symmetry breaking: the cell with lowest coordinates\n",
    "  # should be in the first step.\n",
    "  for i in range(1, max_steps):\n",
    "    solver.Add(x[0] * cols + y[0] < x[i] * cols + y[i])\n",
    "\n",
    "  # symmetry breaking: second step is larger than\n",
    "  # first step\n",
    "  # solver.Add(x[0]*cols+y[0] < x[1]*cols+y[1])\n",
    "\n",
    "  #\n",
    "  # objective\n",
    "  #\n",
    "  objective = solver.Maximize(sum_points, 1)\n",
    "\n",
    "  #\n",
    "  # solution and search\n",
    "  #\n",
    "  # db = solver.Phase(x + y,\n",
    "  #                    solver.CHOOSE_MIN_SIZE_LOWEST_MIN,\n",
    "  #                    solver.ASSIGN_MIN_VALUE)\n",
    "\n",
    "  # Default search\n",
    "  parameters = pywrapcp.DefaultPhaseParameters()\n",
    "\n",
    "  parameters.heuristic_period = 200000\n",
    "  # parameters.var_selection_schema = parameters.CHOOSE_MAX_SUM_IMPACT\n",
    "  parameters.var_selection_schema = parameters.CHOOSE_MAX_AVERAGE_IMPACT  # <-\n",
    "  # parameters.var_selection_schema = parameters.CHOOSE_MAX_VALUE_IMPACT\n",
    "\n",
    "  parameters.value_selection_schema = parameters.SELECT_MIN_IMPACT  # <-\n",
    "  # parameters.value_selection_schema = parameters.SELECT_MAX_IMPACT\n",
    "\n",
    "  # parameters.initialization_splits = 10\n",
    "\n",
    "  db = solver.DefaultPhase(x + y, parameters)\n",
    "\n",
    "  solver.NewSearch(db, [objective])\n",
    "\n",
    "  num_solutions = 0\n",
    "  while solver.NextSolution():\n",
    "    num_solutions += 1\n",
    "    print(\"sum_points:\", sum_points.Value())\n",
    "    print(\"adding 1 to coords...\")\n",
    "    for s in range(max_steps):\n",
    "      print(\"%i %i\" % (x[s].Value() + 1, y[s].Value() + 1))\n",
    "    print()\n",
    "\n",
    "  print(\"\\nnum_solutions:\", num_solutions)\n",
    "  print(\"failures:\", solver.Failures())\n",
    "  print(\"branches:\", solver.Branches())\n",
    "  print(\"WallTime:\", solver.WallTime())\n",
    "\n",
    "\n",
    "# Default problem:\n",
    "# Data from\n",
    "# Mike Trick: \"Operations Research, Sudoko, Rogo, and Puzzles\"\n",
    "# http://mat.tepper.cmu.edu/blog/?p=1302\n",
    "#\n",
    "# This has 48 solutions with symmetries;\n",
    "# 4 when the path symmetry is removed.\n",
    "#\n",
    "rows = 5\n",
    "cols = 9\n",
    "max_steps = 12\n",
    "W = 0\n",
    "B = -1\n",
    "problem = [[2, W, W, W, W, W, W, W, W], [W, 3, W, W, 1, W, W, 2, W],\n",
    "           [W, W, W, W, W, W, B, W, 2], [W, W, 2, B, W, W, W, W, W],\n",
    "           [W, W, W, W, 2, W, W, 1, W]]\n",
    "if len(sys.argv) > 1:\n",
    "  exec(compile(open(sys.argv[1]).read(), sys.argv[1], \"exec\"))\n",
    "main(problem, rows, cols, max_steps)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
